package 最大子序和;

/**
 * @author: AirMan
 * @date: 2025/4/22 10:54
 * @description:
 */
public class Solution {
    public int maxSubArray(int[] nums) {
        // 动态规划
        // 动态转移方程：一个元素只有 选择 or 不选择 两种状态
        // ①： 加入：dp[i] = nums[i] + dp[i - 1]（如果加入当前元素能增大子数组的和）
        // ②： 不加入：dp[i] = nums[i]（如果当前元素比之前的和大，或者不加这个元素更好）
        // 最后返回 Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1])

        if (nums.length == 0) {
            return 0;
        }

        int result = nums[0];
        // dp[1]表示包括i之前的最大连续子序列和
        int[] dp = new int[2];
        dp[0] = dp[1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 状态转移公式
            dp[1] = Math.max(nums[i] + dp[0], nums[i]);
            // dp[0] 记录前 i-1 之前的最大连续子序列和
            dp[0] = dp[1];
            // 判断当前的最大值是否更新
            if (dp[1] > result) {
                result = dp[1];
            }
        }
        return result;
    }
}
